package lru

import "container/list"

// Cache is a LRU cache. It is not safe for concurrent access.
// Cache 是一个 LRU cache。它不是并发安全的。
// LRU(Least Recently Used): 最近最少使用
type Cache struct {
	// 缓存最大的容量，单位字节；
	// groupcache 使用的是最大存放 entry 个数
	maxBytes int64
	//已经使用的字节数
	nbytes int64
	ll     *list.List
	cache  map[string]*list.Element
	//optional and executed when an entry is purged
	// 当一个 entry 从缓存中移除是调用该回调函数，默认为 nil
	// groupcache 中的 key 是任意的可比较类型；value 是 interface{}
	OnEvicted func(key string, value Value) //回调函数
}

type entry struct {
	key   string
	value Value
}

// Value use Len to count how many bytes it takes
type Value interface {
	Len() int
}

// New 创建一个新的 Cache，如果 maxBytes 是 0，表示没有容量限制
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes:  maxBytes,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}

// Get 从 cache 中获取 key 对应的值，nil 表示 key 不存在
func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele) //表示有访问就将该记录放在队列尾部。
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

// RemoveOldest 从 cache 中删除最旧的记录
// RemoveOldest 一般不主动调用，而是在内存满时自动触发（在新增方法中看到了），这就是缓存淘汰
func (c *Cache) RemoveOldest() {
	ele := c.ll.Back() //返回链表的最后一个元素
	if ele != nil {
		c.ll.Remove(ele) //删除该元素
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key) //将该元素从 map 中删除掉
		c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

func (c *Cache) Add(key string, value Value) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		c.nbytes += int64(value.Len()) - int64(kv.value.Len())
		kv.value = value
	} else {
		ele := c.ll.PushFront(&entry{key: key, value: value})
		c.cache[key] = ele
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	//如果容量有限制，且已使用的容量已经超过了最大容量限制，则调用 RemoveOldest() 函数删除最旧的记录
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

// Len 获取缓存记录数
func (c *Cache) Len() int {
	return c.ll.Len()
}
